前言

昨天介紹了Tree的定義跟一些名詞解釋，今天來介紹一個樹的共通特性以及二元樹。

特性

如果一棵樹的有V個node，有E個邊，那麼，

V = E + 1

• 就是一棵樹上的節點數量一定會比邊的數量多1。
• 除了Root以外，其他的node都會有一個邊從其parent node指向自己。
• V = E + 1 對每一種類型的Tree都成立。

二元樹 Binary tree

一棵樹的internal node 最多只會有兩個child nodes。

• 在資料結構中最廣泛使用的樹狀結構是 Binary tree。

• 下圖就是一個Binary tree
  
  可以看出每個node最多只有兩個Subtree。

• 在左邊的Subtree : 左子樹 Left Subtree。

• 在右邊的Subtree : 右子樹 Right Subtree。

• 特性

  1. Binary tree 第k階度的node數量最多是2的k-1次方個
     
  2. Height為 k 的Binary tree，node總數最多會有2的k次方-1個
  3. Height為 k 的Binary tree，node總數最少會有k個
     => 就是每一level至少會有一個node，所以是k個

• 正規二元樹 Formal Binary tree
  Tree的所有internal node都正好有兩個child node。
  

  • internal node 是上圖灰色node，external node則是紅色node
  • external node 會比 internal node 多1個。

• 完整二元樹 Complete Binary tree

  各層節點全滿，除了最後一層，最後一層節點全部靠左。

  • 二元樹的node編號有順序性:
    

  • 從圖可以觀察出，Left Subtree的編號是parent node編號乘上 2。

  • 從圖可以觀察出，Right Subtree的編號是parent node編號乘上 2 加上 1。

參考

細談資料結構 第六版
ISBN 978-986-312-014-8